from typing import List


class Solution:
    """
    根据[22]括号生成问题的dfs模板写出回溯代码
    """

    def __init__(self):
        self.result = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        self.dfs(1, [], self.result, k, n)
        return self.result

    def dfs(self, i, tmp, res, k, n):
        # terminator
        if len(tmp) == k:
            res.append(tmp)
            return
        # process
        for j in range(i, n + 1):
            # drill down
            self.dfs(j + 1, tmp + [j], res, k, n)


if __name__ == '__main__':
    print(Solution().combine(n=8, k=4))
